﻿// 0816train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给定一个乱序的数组，删除所有的重复元素，使得每个元素只出现一次，
 并且按照出现的次数从高到低进行排序，相同出现次数按照第一次出现顺序进行先后排序。

示例1
1,3,3,3,2,4,4,4,5
输出
3,4,1,2,5

 */

struct Node01
{
    int index, value;
    int count = 1;

    void addCount()
    {
        count += 1;
    }
    Node01() = default;
    Node01(int index, int value) :index(index), value(value) {};
};

bool Compare01(Node01&a, Node01&b)
{
    if (a.count==b.count)
    {
        return a.index < b.index;
    }
    return a.count > b.count;
}

void solve01(vector<int>&oh_vec)
{
    //map
    unordered_map<int, Node01>oh_map;

    for (int i=0; i<oh_vec.size(); i++)
    {
        int curr_num = oh_vec[i];
        if (oh_map.count(curr_num)>0)
        {
            oh_map[curr_num].addCount();
        }
        else
        {
            Node01 node(i, curr_num);
            oh_map[curr_num] = node;
        }
	    
    }
    
    vector<Node01>sort_vec;
    for (auto&map_item:oh_map)
    {
        sort_vec.push_back(map_item.second);
    }

    sort(sort_vec.begin(), sort_vec.end(), Compare01);

    vector<int>result_vec;

    for (auto&item:sort_vec)
    {
        result_vec.push_back(item.value);
    }

    for (int i=0; i<result_vec.size(); i++)
    {
	    if (i!=result_vec.size()-1)
	    {
            cout << result_vec[i] << ',';
	    }
        else
        {
            cout << result_vec[i];
        }

    }
   
    //solve01(vector<int>&oh_vec)
}


/*
 有一个字符串数组 words 和一个字符串 chars 。 
假如可以用 chars 中的字母拼写出 words 中的某个“单词”（字符串），那么我们就认为你掌握了这个单词。 
words 的字符仅由 a-z 英文小写字母组成，例如 “abc” chars 由 a-z 英文小写字母和 “?” 组成。其中英文问号 “?” 表示万能字符，能够在拼写时当做任意一个英文字母。
例如：“?” 可以当做 “a” 等字母。 
注意：每次拼写时，chars 中的每个字母和万能字符都只能使用一次。 
输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词，则输出 0。

输入描述
第 1 行输入数组 words 的个数，记为 N。
从第 2 行开始到第 N+1 行一次输入数组 words 的每个字符串元素。
第 N+2 行输入字符串 chars。

输出描述
输出一个整数，表示词汇表 words 中你掌握的单词个数。

输入
4
cat
bt
hat
tree
at?ch
输出
3
 */

class Solution02
{
public:
    int result = 0;

    void checkVerify(string target_str, unordered_map<char, int>&origin_map)
    {
        int available_count = 0;
        if (origin_map.count('?')>0)
        {
            available_count = origin_map['?'];
        }

        unordered_map<char, int>target_map;
        for (auto&oh_char:target_str)
        {
            target_map[oh_char] += 1;
        }

        for (auto&map_item:target_map)
        {
            char target_char = map_item.first;
            char target_count = map_item.second;
            if (origin_map[target_char]< target_count)
            {
                available_count -= (target_count - origin_map[target_char]);
            }
        }

        if (available_count>=0)
        {
            result += 1;
        }

        //checkVerify
    }

    void solve02(vector<string>& str_vec, string origin_str)
    {
        unordered_map<char, int>origin_map;
        for (auto& oh_char : origin_str)
        {
            origin_map[oh_char] += 1;
        }

        for (auto&oh_str:str_vec)
        {
            checkVerify(oh_str, origin_map);
        }
        cout << result;
        //solve02------
    }

};


/*
 实现一个模拟目录管理功能的软件，输入一个命令序列，输出最后一条命令运行结果。
 支持命令： 
1) 创建目录命令：mkdir 目录名称，如mkdir abc为在当前目录创建abc目录，
如果已存在同名目录则不执行任何操作。
此命令无输出。

2) 进入目录命令：cd 目录名称，如cd abc为进入abc目录，
特别地，cd ..为返回上级目录，如果目录不存在则不执行任何操作。此命令无输出。

3) 查看当前所在路径命令：pwd，输出当前路径字符串

约束:
1) 目录名称仅支持小写字母；mkdir和cd命令的参数仅支持单个目录，
如mkdir abc和cd abc;不支持嵌套路径和绝对路径，
如mkdir abc/efg，cd abc/efq是不支持的。
2) 目录符号为/，根目录/作为初始目录。
3) 任何不符合上述定义的无效命令不做任何处理并且无输出。

输入描述
输入N行字符串，每一行字符串是一条命令

输出描述
输出最后一条命令运行结果字符串

输入
mkdir abc
cd abc
pwd
输出
/abc/


 */
 //mkdir就往map里存，
         /*
          {
             '/':{}
             abc:{prev:'/',next:'cde'}
             cde:{prev:'abc'}
          }

         {abc,cde}
          */
class Solution03
{
public:
    struct PathNode
    {
        string name, prev;
        unordered_set<string>next_set;
        void updateNext(string&new_next)
        {
            next_set.insert(new_next);
        }
        PathNode() = default;
        PathNode(string name, string prev) :name(name),prev(prev) {};
    };
    unordered_map<string, PathNode>path_map;
    vector<string>path_stack;

    bool checkVerify(vector<string>&order_vec, string& order_str)
    {
        
        if (order_vec[0]=="mkdir")
        {
            if (order_vec[1].empty())
            {
                return false;
            }

            for (auto&oh_char:order_vec[1])
            {
                bool is_lowcase = oh_char >= 'a' && oh_char <= 'z';
                if (!is_lowcase) return false;
            }
	        
        }
        else if (order_vec[0] == "cd")
        {
            if (order_vec[1].empty())
            {
                return false;
            }
            else if (order_vec[1]=="..")
            {
                return true;
            }
            for (auto& oh_char : order_vec[1])
            {
                bool is_lowcase = oh_char >= 'a' && oh_char <= 'z';
                if (!is_lowcase) return false;
            }
        }
        else if (order_vec[0] == "pwd")
        {
            if (order_str != "pwd") return false;
        }

        return true;
        //checkVerify
    }

    void handleOrder(string&order_str, bool is_end)
    {
        stringstream oh_sstream(order_str);
        string token;
        vector<string>order_vec;
        while (oh_sstream >> token)
        {
            order_vec.push_back(token);
        }

        if (!checkVerify(order_vec, order_str)) return;

        if (order_vec[0]=="mkdir")
        {
            string mk_name = order_vec[1];
            if (path_map.count(mk_name)==0)
            {
                string mk_prev = path_stack[path_stack.size()-1];
                PathNode path_node(mk_name, mk_prev);
                path_map[mk_name] = path_node;

                path_map[mk_prev].updateNext(mk_name);

                //for (auto&str: path_map[mk_prev].next_set)
                //{
                //    cout << str << ' ';
                //}

            }
            //mkdir------
        }
        else if (order_vec[0] == "cd")
        {
            string curr_pos = path_stack[path_stack.size() - 1];
            string next_name = order_vec[1];

            if (next_name==".." && curr_pos!="/")
            {
                path_stack.pop_back();
            }
            else if (path_map[curr_pos].next_set.count(next_name)>0)
            {
                path_stack.push_back(next_name);
            }

            //cd
        }
        else if (order_vec[0] == "pwd")
        {
            if (!is_end) return;
            /*
             *  /abc/
             *  */
            string curr_path_name;

            for (int i=0; i<path_stack.size();i++)
            {
                string name = path_stack[i];
                curr_path_name += name;
                if (i!=0)
                {
                    curr_path_name += '/';
                }
            }

            cout << curr_path_name;
            //pwd------
        }

        //handleOrder
    }

    void solve03(vector<string>&path_vec)
    {
        //初始化stack和map,添加根目录
        string root_name = "/";
        path_stack.push_back(root_name);
        PathNode path_node(root_name, "");
        path_map[root_name] = path_node;

        //for (auto&order_str:path_vec)
        //{
        //    handleOrder(order_str);
        //}

        for (int i=0; i<path_vec.size(); i++)
        {
            bool is_end = i == path_vec.size() - 1;
            string order_str = path_vec[i];
            handleOrder(order_str, is_end);
        }

        //solve03
    }

};


int main()
{
	{
        vector<string>str_vec = { "mkdir abc","cd abc","cd ..","cd ..","pwd" };
        Solution03 solu03;
        solu03.solve03(str_vec);
        return 0;
        //string order_str = "pwd abc";
        //vector<string>order_vec = { "pwd","abc" };

        //Solution03 solu03;
        //cout << solu03.checkVerify(order_vec, order_str);

        //return 0;
	}
	{
        /*
         mkdir abc
        cd abc
        pwd
         */
        //vector<string>str_vec = {"mkdir abc","cd abc","pwd"};
        //vector<string>str_vec = { "mkdir abc","cd abc","pwd" };
        vector<string>str_vec;
        string input;
        while (getline(cin, input))
        {
            if (input.empty())
            {
                break;
            }
            str_vec.push_back(input);
        }

        Solution03 solu03;
        solu03.solve03(str_vec);

        return 0;
	}
	{
        /*
         mkdir abc
		cd abc
		pwd
         */

        string str = "pwd";
        stringstream oh_sstream(str);
        string token;
        vector<string>order_vec;
        while (oh_sstream>>token)
        {
            order_vec.push_back(token);
        }

        cout << order_vec[0];

        return 0;
	}

	{

		/*
4
cat
bt
hat
tree
at?ch
 */
        int vec_size;
        cin >> vec_size;
        vector<string>str_vec(vec_size);

        for (int i=0; i<vec_size; i++)
        {
            cin >> str_vec[i];
        }

        string origin_str;
        cin >> origin_str;

        //cout << origin_str;

        //vector<string>str_vec = {"cat","bt","hat","tree"};
        //string origin_str = "at?ch";

        Solution02 solu;
        solu.solve02(str_vec, origin_str);

        return 0;
	}


    //1,3,3,3,2,4,4,4,5
    vector<int>oh_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (getline(oh_sstream,token,','))
    {
        oh_vec.push_back(stoi(token));
    }

    //for (auto&num:oh_vec)
    //{
    //    cout << num << ',';
    //}

    //vector<int>oh_vec = { 1,3,3,3,2,4,4,4,5 };
    solve01(oh_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
